#include <iostream>
#include <vector>
#include <ctime>
#include <iomanip>
#include "BalanceTree.h"

using namespace std;

template <typename T>
void Avl_sort(vector<T> &_a)
{
     AvlTree<T> h;
     for(int i=0;i<_a.size();i++)
     {
	 h.insert(_a[i]);
     }
     _a.clear();
     
     while(h.isEmpty()!=true)
     {
	 _a.push_back(h.findMin());
	 h.remove(h.findMin());
	
     }
}

template<typename T>
void Splay_sort(vector<T> &_a)
{
     SplayTree<T> t;
     for(int i=0;i<_a.size();i++)
     {
	 t.insert(_a[i]);
     }
     _a.clear();
    
     while(t.isEmpty()!=true)
     {
	 _a.push_back(t.findMin());
	 t.remove(t.findMin());
	
     }
}

int main()
{
     clock_t start,end;//定义时间变量
     srand((unsigned)time(NULL));//播种一个时间相关乱码打乱随机顺序
     int n;
     std::cin >> n;
     std::cout << "Test : n ramdom numbers.Use Randomized sort." <<std::endl;//n个数据
     vector<int> a,b;
     for(int i = 0; i < n; i++)
    {
         int x = rand() & 65535;//控制范围
         a.push_back(x);
         b.push_back(x);
    }
     start = clock();//AVL初始时间
     Avl_sort(a);
     end = clock();//AVL结束时间
     double endtime = (double)(end - start)/CLOCKS_PER_SEC;
     cout << "AvlTree   : " << endtime*1000 << "ms" <<endl;
     start = clock();//Splay开始时间
     Splay_sort(b);
     end = clock();//Splay结束时间
     endtime = (double)(end - start)/CLOCKS_PER_SEC;//神奇操作 没有不行 不明觉厉
     cout << "SplayTree : " << endtime*1000 << "ms" <<endl;
     //分别输出AVL和Splay用时


}
